package com.lin.codesnippet.sort;

import com.lin.enums.codesnippet.SortStatusCode;
import com.lin.codesnippet.sort.util.SortUtil;

/**
 * 插入排序
 * <p>O(n)~O(n^2)~O(n^2)</p>
 * 稳定
 *
 * @author linqiankun
 */
public class InsertionSort {


    /**
     * 插入排序
     *
     * @param array          需要排序的数组
     * @param sortStatusCode 排序方式
     */
    public static void insertionSorted(int[] array, SortStatusCode sortStatusCode) {
        //默认第0个是排好序的,i以前的排好序
        for (int i = 1; i < array.length; i++) {
            int get = array[i];
            int j = i - 1;
            //从当前位值倒序往前查找
            while (j >= 0 && sortStatusCode.getCode() == SortUtil.compare(get, array[j])) {
                array[j + 1] = array[j];
                j--;
            }
            //不满足比较条件时放在位置的右边
            array[j + 1] = get;
        }

    }

    /**
     * 二分插入排序
     *
     * @param array          需要排序的数组
     * @param sortStatusCode 排序方式
     */
    public static void insertionSortedDichotomy(int[] array, SortStatusCode sortStatusCode) {
        for (int i = 1; i < array.length; i++) {
            int get = array[i];
            int left = 0;
            int right = i - 1;
            //二分查找数据所处的位置，也是在之前的队列中
            while (left <= right) {
                int mid = (left + right) / 2;
                if (sortStatusCode.getCode() == SortUtil.compare(get, array[mid]))
                // if (array[mid] > get)
                {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            //拿走的是位置i的数据，left之后的往后移动
            if (i - left >= 0) {
                System.arraycopy(array, left, array, left + 1, i - left);
            }
            array[left] = get;
        }
    }

}
